package com.example.algorithms.others;

/**
 * @Author Zhang Jie
 * @Date 10/20/20
 * @Version 1.0
 */

/**
 * 二分查找
 */
public class BinarySearch {

    /**
     * 只返回一个下标即可
     * @param arr 有序数组
     * @param target 要查找的数字
     * @return 找到的一个下标
     */
    public int findSingle(int[] arr, int target){

        int left=0;
        int right=arr.length-1;

        while(left<=right){
            int mid=(left+right)/2;
            if(arr[mid]==target){
                return mid;
            }else if(arr[mid]>target){
                right=mid-1;
            }else if(arr[mid]<target){
                left=mid+1;
            }
        }

        return -1;
    }

    /**
     * 返回左侧边界--小于target的值有几个，如[2,3,5,7]的target=1,则返回0；target=8返回4
     * @param arr 已排序数组 [1,2,2,2,3]
     * @param target 2
     * @return 1
     * 也可以修改为找不到值返回-1
     */
    public int findLeftBoundary(int[] arr, int target){
        int left=0;
        int right=arr.length;
        while(left<right){
            int mid=(left+right)/2;
            if(arr[mid]==target){
                right=mid;
            }else if(arr[mid]>target){
                right=mid;//可以和上面的合并为一句
            }else if(arr[mid]<target){
                left=mid+1;
            }
        }

         // return left;//返回小于target的值有几个，left==right

        //region 找不到返回-1
        //当target比所有数都大的时候，left=arr.length，单算防止溢出
        if(left==arr.length){
            return -1;
        }
        //当target比所有数都小，left=0;
        //当left>0但没有target时,arr[left]>target
        return arr[left]==target? left:-1;
        //end region
    }

    /**
     * 返回右侧边界,<=target的最右侧的值的索引
     * @param arr 已排序数组 [1,2,2,2,3]
     * @param target 2
     * @return 3
     */
    public int findRightBoundary(int[] arr, int target){
        int left=0;
        int right=arr.length;
        while(left<right){
            int mid=(left+right)/2;
            if(arr[mid]==target){
                left=mid+1;
            }else if(arr[mid]<target){
                left=mid+1;
            }else if(arr[mid]>target){
                right=mid;
            }
        }
        //return left-1;//返回<=target的最右侧边界
        //region 找不到返回-1
        if(left==0){
            return -1;
        }

        return arr[left-1]==target?(left-1):-1;
        //end region
    }
}
